The invention is related to a method and a device for encoding a bit sequence.
Bit sequences results, for instance, from encoding digital multimedia content like audio, video, combinations thereof or side information accompanying such content. Encoding such bit sequences for compact representation of at least one of the encoded content and the side information is crucial for efficient use of storage capacities and transmission bandwidth.
Each bit sequence, which is not a trivial bit sequence consisting either only of Zeroes or only of Ones, may also be understood as consisting of one or more runs of Zeroes alternating with one or more runs of Ones wherein each run is a contiguous sub-sequence of one or more equally valued bits which is immediately followed and immediately preceded by another run of bits each having a different bit value as long as the run is neither the very first nor the very last run of the bit sequence.
In bit sequences, bits of a first possible bit value and bits of a different second possible bit value commonly occur with significantly different frequencies, e.g. Zeroes are more likely than Ones or vice versa. Then, entropy of the bit sequence is smaller than the number of bits comprised in the bit sequence.
If so, there is redundancy in the bit sequence which can be removed by lossless compression.
It is known to use an entropy coding method for lossless compression of bit sequences. Basically, there are three kinds of entropy coding method: (1) variable length coding (VLC), like Huffman coding, (2) arithmetic coding, and (3) dictionary-based compression, like Lempel-Ziv compression or Lempel-Ziv-Welch compression.
The effect of entropy coding is that, difference between entropy of the compressed bit sequence and number of bits comprised in the compressed bit sequence is smaller than difference between entropy of and number of bits comprised in the bit sequence prior to compression.
There is ongoing effort in the art for an alternative approaches in principle adapted for improving encoding.